//给定一棵二叉搜索树，请找出其中第k大的节点。 
//
// 
//
// 示例 1: 
//
// 输入: root = [3,1,4,null,2], k = 1
//   3
//  / \
// 1   4
//  \
//   2
//输出: 4 
//
// 示例 2: 
//
// 输入: root = [5,3,6,2,4,null,null,1], k = 3
//       5
//      / \
//     3   6
//    / \
//   2   4
//  /
// 1
//输出: 4 
//
// 
//
// 限制： 
//
// 1 ≤ k ≤ 二叉搜索树元素个数 
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 
// 👍 190 👎 0


package leetcode.editor.cn1;

import com.leetcode.entity.TreeNode;

//Java：二叉搜索树的第k大节点

/**
 * 给定一棵二叉搜索树，请找出其中第k大的节点。
 * 二叉搜索树：左节点 < 中节点 < 右节点
 */
public class ErChaSouSuoShuDeDiKdaJieDianLcof {
    public static void main(String[] args) {
        Solution solution = new ErChaSouSuoShuDeDiKdaJieDianLcof().new Solution();
        // TO TEST
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        System.out.println(solution.kthLargest(root, 1));

    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    class Solution {

        public int k;

        public int res;

        public int kthLargest(TreeNode root, int k) {
            // 中序遍历：左中右 or 右中左，即可计算出第K大的节点
            this.k = k;
            dfs(root);
            return res;
        }

        public void dfs(TreeNode node) {
            if (node == null)
                return;
            // 遍历右子树
            dfs(node.right);
            // 第一次访问到的节点，就是第一大节点    n = k
            // 第二次访问到的节点，就是第二大节点
            // 第三次访问到的节点，就是第三大节点
            // 第k次访问到的节点，就是第k大节点    n = 1，因此n = 0时直接返回，不在遍历后面的节点
            if (k == 0)
                return;
            if (--k == 0) {
                res = node.val;
                return;
            }
            // 遍历左字数
            dfs(node.left);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
